Fundamental Theorem of Arithmetic

Note that by taking \(1\) as an empty product we can extend this result to \(n \geq 1\).

To prove this we will first prove a weaker result with non-uniqueness.

Proof

We proceed with strong induction as follows. First note that because \(2\) is prime, \(2\) is expressible as a product of primes.

Now assume than for all \(k\) satisfying \(2 \leq k \leq n - 1\), \(k\) can be written as a product of primes.

Suppose \(n\) is prime, then clearly it is a singleton product of primes. If \(n\) is not prime, then it factors as \(n = ab\) where \(1 < a,b < n\). Applying the hypothesis to \(k = a\) and \(k = b\) we have

where all \(p_i\) and \(q_j\) are prime. Therefore

a product of primes.

We can now prove uniqueness.

Proof

Assume that \(n = p_1 \dots p_k = q_1 \dots q_s\) are two factorisations of \(n\) into a product of primes. Then \(p_i \mid q_1 \dots q_s\) for each \(i\), and so by Euclid's lemma we know that \(p_i\) divides one of \(q_1, \dots, q_s\), say \(q_j\). However the only divisors of \(q_j\) are \(1\) and \(p_i\), and \(p_i \neq 1\) by assumption that it is prime. Hence \(p_i = q_j\).

Repeating this procedure and removing factors, we are able to pair them uniquely, and also conclude that \(s = k\).